import java.util.PriorityQueue;

public class Leetcode {
}

//leetcode:860:柠檬水找零
class Solution1 {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for(int x : bills){
            //记录5元的个数
            if(x == 5) five++;
                //如果收到10元，要找5元
            else if (x == 10) {
                //5元的个数不为0，就将一个5元找出，并让5元个数减一，10元个数加1
                if(five == 0) return false;
                five--;
                ten++;
            }
            //如果收到20元，要找15元
            else if (x == 20){
                //如果5元和10元的个数都不为零，就找一个10和一个5元
                if (five != 0 && ten != 0){
                    five--;
                    ten--;
                } else if (five >= 3){//如果没有10且，5元的个数大于3个，就找3个五元
                    five -= 3;
                } else {//如果都不成立，就无法进行找钱，返回false
                    return false;
                }
            }
        }
        return true;
    }
}

//leetcode:2208:将数组和减半的最小操作次数
class Solution2 {
    public int halveArray(int[] nums) {
        //将数组放入优先级队列中按照从大到小排序
        PriorityQueue<Double> q = new PriorityQueue<>((a, b) -> b.compareTo(a));
        double sum = 0.0;
        for(int x : nums){
            q.offer((double) x);
            sum += x;
        }
        //得到一半数组的大小
        sum /= 2.0;

        //计数器，作为将sum减到小于0的次数
        int count = 0;
        while(sum > 0){
            //得到队首元素，进行减半
            double t = q.poll() / 2.0;
            //让sum减去这最大数的一半
            sum -= t;
            //记录次数
            count++;
            //将这一半放入队列中，重新进行排序
            q.offer(t);
        }
        return count;
    }
}